乘积|被减数_算法1913.两个数对之间的最大乘积差（java/c/c++/python/go/rust）

篇首语：本文由编程笔记#小编为大家整理，主要介绍了算法1913. 两个数对之间的最大乘积差（java / c / c++ / python / go / rust）相关的知识，希望对你有一定的参考价值。

---

文章目录

• 1913. 两个数对之间的最大乘积差&＃xff1a;
• 样例 1&＃xff1a;
• 样例 2&＃xff1a;
• 提示&＃xff1a;
• 分析
• 题解
• • java
  • c
  • c&＃43;&＃43;
  • python
  • go
  • rust
  
  
• 原题传送门&＃xff1a;https://leetcode-cn.com/problems/maximum-product-difference-between-two-pairs/

---

1913. 两个数对之间的最大乘积差&＃xff1a;

两个数对 (a, b) 和 (c, d) 之间的 乘积差 定义为 (a * b) - (c * d) 。

• 例如&＃xff0c;(5, 6) 和 (2, 7) 之间的乘积差是 (5 * 6) - (2 * 7) &＃61; 16 。

给你一个整数数组 nums &＃xff0c;选出四个 不同的 下标 w、x、y 和 z &＃xff0c;使数对 (nums[w], nums[x]) 和 (nums[y], nums[z]) 之间的 乘积差 取到 最大值 。

返回以这种方式取得的乘积差中的 最大值 。

样例 1&＃xff1a;

输入&＃xff1a;
nums &＃61; [5,6,2,7,4]

输出&＃xff1a;
34

解释&＃xff1a;
可以选出下标为 1 和 3 的元素构成第一个数对 (6, 7) 以及下标 2 和 4 构成第二个数对 (2, 4)
乘积差是 (6 * 7) - (2 * 4) &＃61; 34

样例 2&＃xff1a;

输入&＃xff1a;
nums &＃61; [4,2,5,9,7,4,8]

输出&＃xff1a;
64

解释&＃xff1a;
可以选出下标为 3 和 6 的元素构成第一个数对 (9, 8) 以及下标 1 和 5 构成第二个数对 (2, 4)
乘积差是 (9 * 8) - (2 * 4) &＃61; 64

提示&＃xff1a;

• 4 <&＃61; nums.length <&＃61;
  
  
  
  
  1
  
  
  
  0
  
  
  4
  
  
  
  
  10^4
  
  
  104
• 1 <&＃61; nums[i] <&＃61;
  
  
  
  
  1
  
  
  
  0
  
  
  4
  
  
  
  
  10^4
  
  
  104

---

分析

• 面对这道算法题目&＃xff0c;首先可以想一下两个正整数如何形成最大差值&＃xff1f;
• 被减数尽可能大&＃xff0c;减数尽可能小&＃xff0c;就可以有最大差值。
• 两个正整数的乘积怎么尽可能大呢&＃xff1f;
• 两个正整数尽可能大&＃xff0c;他们的乘积就会最大化&＃xff1b;反之两个正整数尽可能小&＃xff0c;他们的乘积就会最小化。
• 所以我们其实要找出最大的两个数和最小的两个数。
• 最大的两个数相乘作为被减数&＃xff0c;最小的两个数相乘作为减数。
• 在一个无序整数数组中如何找到两个最大值和两个最小值呢&＃xff1f;
• 首先想到&＃xff0c;可以先排序&＃xff0c;然后取最前面两个数和最后面两个数。但是排序至少需要O(nlogn)的时间复杂度。
• 事实上我们只需要遍历一次&＃xff0c;记录下最大的两个数和最小的两个数就可以了。

---

题解

java

class Solution
public int maxProductDifference(int[] nums)
int max1 &＃61; 0;
int max2 &＃61; 0;
int min1 &＃61; 10001;
int min2 &＃61; 10001;
for (int num : nums)
if (num > max1)
max2 &＃61; max1;
max1 &＃61; num;
else if (num > max2)
max2 &＃61; num;

if (num < min1)
min2 &＃61; min1;
min1 &＃61; num;
else if (num < min2)
min2 &＃61; num;


return max1 * max2 - min1 * min2;




---

c

int maxProductDifference(int* nums, int numsSize)
int max1 &＃61; 0;
int max2 &＃61; 0;
int min1 &＃61; 10001;
int min2 &＃61; 10001;
for (int i &＃61; 0; i < numsSize; &＃43;&＃43;i)
int num &＃61; nums[i];
if (num > max1)
max2 &＃61; max1;
max1 &＃61; num;
else if (num > max2)
max2 &＃61; num;

if (num < min1)
min2 &＃61; min1;
min1 &＃61; num;
else if (num < min2)
min2 &＃61; num;


return max1 * max2 - min1 * min2;



---

c&＃43;&＃43;

class Solution
public:
int maxProductDifference(vector<int>& nums)
int max1 &＃61; 0;
int max2 &＃61; 0;
int min1 &＃61; 10001;
int min2 &＃61; 10001;
for (int num: nums)
if (num > max1)
max2 &＃61; max1;
max1 &＃61; num;
else if (num > max2)
max2 &＃61; num;

if (num < min1)
min2 &＃61; min1;
min1 &＃61; num;
else if (num < min2)
min2 &＃61; num;


return max1 * max2 - min1 * min2;

;


---

python

class Solution:
def maxProductDifference(self, nums: List[int]) -> int:
max1 &＃61; 0
max2 &＃61; 0
min1 &＃61; 10001
min2 &＃61; 10001
for num in nums:
if num > max1:
max2 &＃61; max1
max1 &＃61; num
elif num > max2:
max2 &＃61; num
if num < min1:
min2 &＃61; min1
min1 &＃61; num
elif num < min2:
min2 &＃61; num;
return max1 * max2 - min1 * min2



---

go

func maxProductDifference(nums []int) int
max1 :&＃61; 0
max2 :&＃61; 0
min1 :&＃61; 10001
min2 :&＃61; 10001
for _, num :&＃61; range nums
if num > max1
max2 &＃61; max1
max1 &＃61; num
else if num > max2
max2 &＃61; num

if num < min1
min2 &＃61; min1
min1 &＃61; num
else if num < min2
min2 &＃61; num


return max1*max2 - min1*min2



---

rust

impl Solution
pub fn max_product_difference(nums: Vec<i32>) -> i32
let mut max1 &＃61; 0;
let mut max2 &＃61; 0;
let mut min1 &＃61; 10001;
let mut min2 &＃61; 10001;
nums.iter().for_each(|num|
if *num > max1
max2 &＃61; max1;
max1 &＃61; *num;
else if *num > max2
max2 &＃61; *num;

if *num < min1
min2 &＃61; min1;
min1 &＃61; *num;
else if *num < min2
min2 &＃61; *num;

);
max1 * max2 - min1 * min2




---

---

原题传送门&＃xff1a;https://leetcode-cn.com/problems/maximum-product-difference-between-two-pairs/

---

非常感谢你阅读本文~
欢迎【&＃x1f44d;点赞】【⭐收藏】【&＃x1f4dd;评论】~
放弃不难&＃xff0c;但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子&＃xff1a;https://le-yi.blog.csdn.net/ 博客原创~

---